package 算法;

import testJ.S;

import java.util.*;

public class 队列栈 {

    public static void main(String[] args) {

        队列栈 b = new 队列栈();
        List<List<Integer>> r = new ArrayList<>();
        List<Integer> r1 = new ArrayList<>();
    }
    public int lengthOfLIS(int[] nums) {
        int[] max = new int[nums.length];
        int l = max.length;
        for (int i = 0; i < max.length; i++) {
            int val = nums[i];
            max[i] = 1;
            for (int j = i-1; j >= 0 ; j--) {
                if(val > nums[j]){
                    max[i] = max[j] +1;
                }
            }
        }
        int i = 0;
        for (int max1 : max) {
            i = i>max1?i:max1;
        }
        int i3 = i-1;
        int r = 0;

        for (int i1 = 0; i1 < max.length; i1++) {
            if(i == max[i1]){
                if(i == 1) r++;
                else {
                    for (int i2 = i1-1;i2>=0;i2--){
                        if(max[i2] == i3) r++;
                    }
                }
            }
        }
        return r;
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> room = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        rooms.get(0).forEach(e->{
            stack.push(e);
        });
        room.add(0);
        while (!stack.isEmpty()){
            int i = stack.pop();
            if(room.contains(i)) continue;
            rooms.get(i).forEach(e->{
                stack.push(e);
            });
        }

        return room.size() == rooms.size() ?true:false;
    }
    public int[][] updateMatrix(int[][] matrix) {
        int len1 = matrix.length;
        int len2 = matrix[0].length;
        int j = len1*len2;
        for (int i = 0; i < len1; i++) {
            for (int i1 = 0; i1 < len2; i1++) {
                if(matrix[i][i1] != 0)  matrix[i][i1]= j;
            }
        }
        for (int i = 0; i < len1; i++) {
            for (int i1 = 0; i1 < len2; i1++) {
                Stack<Xy> stack = new Stack();
                if(matrix[i][i1] == 0){
                    stack.push(new Xy(i,i1));
                    while (!stack.isEmpty()){
                        Xy xy = stack.pop();
                        if(xy.x + 1 < len1 && matrix[xy.x][xy.y]+1 < matrix[xy.x+1][xy.y]){
                            matrix[xy.x+1][xy.y] = matrix[xy.x][xy.y]+1;
                            stack.push(new Xy(xy.x+1,xy.y));
                        }
                        if(xy.x - 1 > -1 && matrix[xy.x][xy.y]+1 < matrix[xy.x-1][xy.y]){
                            matrix[xy.x-1][xy.y] = matrix[xy.x][xy.y]+1;
                            stack.push(new Xy(xy.x-1,xy.y));
                        }
                        if(xy.y - 1 > -1 && matrix[xy.x][xy.y]+1 < matrix[xy.x][xy.y-1]){
                            matrix[xy.x][xy.y-1] = matrix[xy.x][xy.y]+1;
                            stack.push(new Xy(xy.x,xy.y-1));
                        }
                        if(xy.y + 1 < len2 && matrix[xy.x][xy.y]+1 < matrix[xy.x][xy.y+1]){
                            matrix[xy.x][xy.y+1] = matrix[xy.x][xy.y]+1;
                            stack.push(new Xy(xy.x,xy.y+1));
                        }
                    }
                }
            }
        }
        return matrix;
    }
    class Xy{
        public int x;
        public int y;

        public Xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        return floodFill2(image,sr,sc,newColor,image[sr][sc]);


    }
    public int[][] floodFill2(int[][] image, int sr, int sc, int newColor,int old) {
        if(sc < 0 || sr < 0 || sr >= image.length || sc >= image[0].length) return image;
        if(image[sr][sc] == newColor || image[sr][sc] != old) return image;

        image[sr][sc] = newColor;

        floodFill2(image,sr-1,sc,newColor,old);
        floodFill2(image,sr+1,sc,newColor,old);
        floodFill2(image,sr,sc-1,newColor,old);
        floodFill2(image,sr,sc+1,newColor,old);
        return image;
    }
    //1000等于0
    public int findTargetSumWays(int[] nums, int S) {
        int[][] pd = new int[nums.length][2001];
        pd[0][nums[0]+1000 ] = 1;
        pd[0][-nums[0]+1000 ] = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < 2001; j++) {

            }
        }
        return 0;
    }
    public Node cloneGraph(Node node) {
        if(node == null) return node;
        Node res = new Node(node.val);
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack1 = new Stack<>();
        stack.push(node);
        stack1.push(res);

        Set<Node> over = new HashSet<>();
        Node t1,t2;
        Node temp;
        while (!stack.isEmpty()){
            t1 = stack.pop();
            over.add(t1);
            t2 = stack1.pop();
            for (int i = 0; i < t1.neighbors.size(); i++) {
                if(over.contains(t1.neighbors.get(i))) continue;
                temp = new Node(t1.neighbors.get(i).val);
                t2.neighbors.add(temp);
                stack.push(t1.neighbors.get(i));
                stack1.push(temp);
            }
        }
        return res;
    };
    public int evalRPN(String[] tokens) {
        if(tokens.length < 1) return 0;
        Stack<String> stack = new Stack();

        int k1,k2;
        for (int i = 0; i < tokens.length; i++) {
            String temp = tokens[i];

            switch (temp){
                case "+":
                    k1 = Integer.parseInt(stack.pop());
                    k2 = Integer.parseInt(stack.pop());
                    stack.push(""+(k1+k2));
                    break;
                case "-":
                    k1 = Integer.parseInt(stack.pop());
                    k2 = Integer.parseInt(stack.pop());
                    stack.push(""+(k2-k1));
                    break;
                case "*":
                    k1 = Integer.parseInt(stack.pop());
                    k2 = Integer.parseInt(stack.pop());
                    stack.push(""+(k2*k1));
                    break;
                case "/":
                    k1 = Integer.parseInt(stack.pop());
                    k2 = Integer.parseInt(stack.pop());
                    stack.push(""+(k2/k1));
                    break;
                default:
                    stack.push(temp);
            }
        }
        return Integer.parseInt(stack.pop());
    }
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack();
        int len = T.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            if(stack.isEmpty())
                stack.push(i);
            else if(T[stack.peek()] < T[i]) {
                while (!stack.isEmpty() || T[stack.peek()] < T[i]) {
                    int t = stack.pop();
                    res[t] = i - t;
                }
                stack.push(i);
            }
        }
        return res;
    }
    public int numSquares(int n) {
        if(n < 2){
            return n;
        }

        int[] num = new int[n+1];
        for (int i = 1; i*i <= n; i++) {
            num[i*i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if(num[i] == 1){
                continue;
            }else {
                num[i] = n+1;
            }
            int t1 = i/2;
            int min = n+1;
            for (int j = i-1; j >= t1; j--){
                min = min < num[j]+num[i-j] ? min:num[j]+num[i-j];
            }
            num[i] = min;
        }
        return num[n];
    }







    int rlen;
    int r0len;
    public void wallsAndGates(int[][] rooms) {
        if(rooms.length < 1){
            return;
        }
        rlen = rooms.length;
        r0len = rooms[0].length;
        for (int i = 0; i < rlen; i++) {
            for (int i1 = r0len - 1; i1 >= 0; i1--) {
                if(rooms[i][i1] == 0)
                    tianShi(rooms,i,i1);
            }
        }
    }
    //rooms[i][j]表示门,值为0，会上下左右比较，会初始化周围inf
    public void tianShi(int[][] rooms,int i,int j){
        int ij = rooms[i][j];
        if(i-1 >= 0 && rooms[i-1][j] >ij+1){
            rooms[i-1][j] = ij+1;
            tianShi(rooms,i-1,j);
        }
        if(j-1 >= 0 && rooms[i][j-1] >ij+1){
            rooms[i][j-1] = ij+1;
            tianShi(rooms,i,j-1);
        }

        if(i+1 < rlen && rooms[i+1][j] > ij+1){
            rooms[i+1][j] = ij+1;
            tianShi(rooms,i+1,j);
        }
        if(j+1 < r0len && rooms[i][j+1] > ij+1){
            rooms[i][j+1] = ij+1;
            tianShi(rooms,i,j+1);
        }
    }
    public int numIslands(char[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int daoyu = 0;
        int l1 = grid.length,l2=grid[0].length;
        for (int i = 0; i < l1; i++) {
            for (int i1 = 0; i1 < l2; i1++) {
                //开始弄岛屿
                if(grid[i][i1] == '1'){
                    queue.add(new int[]{i,i1});
                    grid[1][i1] = '0';
                    while (!queue.isEmpty()){
                        int[] a = queue.poll();

                        int t1 = a[0];
                        int t2 = a[1];


                        if(t2+1 < l2 && grid[t1][t2+1] == '1'){
                            queue.add(new int[]{t1,t2+1});
                            grid[t1][t2+1] = '0';
                        }
                        if(t1+1 < l1 && grid[t1+1][t2] == '1'){
                            queue.add(new int[]{t1+1,t2});
                            grid[t1+1][t2] = '0';
                        }

                        if(t2-1 >= 0 && grid[t1][t2-1] == '1'){
                            queue.add(new int[]{t1,t2-1});
                            grid[t1][t2-1] = '0';
                        }
                        if(t1-1 >= 0 && grid[t1-1][t2] == '1'){
                            queue.add(new int[]{t1-1,t2});
                            grid[t1-1][t2] = '0';
                        }


                    }
                    daoyu++;
                }


            }
        }
        return daoyu;
    }
}
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
class MinStack {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty()){
            stack2.push(x);
        }else
            stack2.push(Math.min(x,stack2.peek()));
    }

    public void pop() {
        stack2.pop();
        stack1.pop();
    }

    public int top() {
return stack1.peek();
    }

    public int getMin() {
return stack2.peek();
    }
}
class MovingAverage {
    int[] m;
    int j = 0;
    int sum = 0;
    int leng;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        m = new int[size];
        leng = m.length;
    }

    public double next(int val) {
        sum = sum+val;
        if(j >= leng){
            sum-= m[j%leng];
        }
        m[j%leng] = val;

        double ss =  1.0 * sum / (j++>=leng ? leng:(j));

        return ss;
    }
}

class MyCircularQueue {

    int[] queue;
    int start = 1,end = 0; //start指向当前要插入的位置,0指向标志符，无效数据
    public int addOne(int i){
        return i+1>=queue.length ? 0:i+1;
    }
    public int subOne(int i){
        return i-1<0 ? queue.length-1:i-1;
    }
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        queue = new int[k+1];  //多预留一个空间，表示结束
    }
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(start == end){
            return false;
        }
        queue[start] = value;
        start = addOne(start);
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(start == addOne(end)) return false;
        end = addOne(end);
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(addOne(end) == start) return -1;
        return queue[addOne(end)];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if(subOne(start) == end) return -1;
        return queue[subOne(start)];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        if(addOne(end) == start) return true;
        return false;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        if(start == end) return true;
        return false;
    }
}
